﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Algoritmia.Problems.Closures
{
    public class WarshallMatrixTransitiveClosureFinder : IMatrixTransitiveClosureFinder
    {
        private readonly Func<IEnumerable<IEnumerable<bool>>, bool[][]> _createMatrix;

        public WarshallMatrixTransitiveClosureFinder(Func<IEnumerable<IEnumerable<bool>>,bool[][]> createMatrix = null)
        {
            _createMatrix = createMatrix ?? (it => (from e in it
                                                    select e.ToArray()).ToArray());   
        }

        public bool[][] TransitiveClosure(bool[][] matrix)
        {
            var n = matrix.Length;
            var result = _createMatrix(matrix);

            for (int k = 0; k < n; k++)
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        result[i][j] = result[i][j] || (result[i][k] && result[k][j]);

            return result;
        }
    }
}
